Dimension de Vapnik-Chervonenkis \(\operatorname{dim}_\text{VC}(\mathcal S)\) de \(\mathcal S\)
Plus petit entier \(h\) tel que le Coefficient de pulvérisation \(N_\mathcal S\) cesse de croître de manière exponentiel. $$N_\mathcal S(l)=2^l\text{ si }l\leqslant h\quad\text{ et }\quad N_\mathcal S(h+1)\lt 2^{h+1}$$

• si un tel entier n'existe pas, on dit que \(\mathcal S\) est de dimension de Vapnik-Chervonenkis infinie
• si \(\mathcal S=\) \(\{\Bbb 1_{f(x)\gt 0}\mid f\in V\}\) ou \(\mathcal S=\{\Bbb 1_{f(x)\geqslant0}\mid f\in V\}\) avec \(V\) un sev de fonctions \(\mathcal X\to{\Bbb R}\) de dimension \(h\), alors \(\operatorname{dim}_\text{VC}(\mathcal S)\) \(\leqslant h\)
    
• si \(\mathcal S\) est l'ensemble des fonctions indicatrices de demi-hyperplans affines de \({\Bbb R}^d\), i.e. \(\mathcal S=\{\Bbb 1_{\langle{w,x}\rangle +b\geqslant0}\mid w\in{\Bbb R}^d,b\in{\Bbb R}\}\), alors \(\operatorname{dim}_\text{VC}(\mathcal S)\) \(\leqslant d+1\)
    
• si \(\mathcal S\) est l'ensemble des indicatrices de boules de \({\Bbb R}^d\), i.e. \(\mathcal S=\{\Bbb 1_{x\in B(a,r)}\mid a\in{\Bbb R}^d,r\geqslant0\}\), alors \(\operatorname{dim}_\text{CV}(\mathcal S)\) \(\leqslant d+2\)
    
• si \(\mathcal S\) est l'ensemble des Ellipsoïdes centrées, i.e. \(\mathcal S=\{\Bbb 1_{\langle{x,\Sigma x}\rangle \leqslant1}\mid\Sigma\text{ symétrique positive }\}\), alors \(\operatorname{dim}_\text{VC}(\mathcal S)\) \(\leqslant\frac{d(d+1)}2+1\)

START
Ω Basique (+inversé optionnel)
Recto: Dire pourquoi le concept de dimension de Vapnik-Chervonenkis est important.
Verso: C'est parce que la croissance de \(N_\mathcal S(l)\) en fonction de \(l\) exprime la complexité de la famille \(\mathcal S\).
Bonus: Théorème de Vapnik-Chervonenkis Carte inversée ?:
END
START
Ω Basique (+inversé optionnel)
Recto: Donner un contre-exemple permettant d'affirmer que la dimension de Vapnik-Chervonenkis n'est pas donnée par le nombre de paramètres.
Verso: $$\mathcal X={\Bbb R}\quad\text{ avec }\quad\mathcal S=\{\Bbb 1_{\sin(\alpha x)\gt 0}\mid\alpha\in{\Bbb R}\}$$ on a alors \(\operatorname{dim}_\text{VC}(\mathcal S)=+\infty\).
Bonus:
Carte inversée ?:
END
START
Ω Basique (+inversé optionnel)
Recto: Illustrer la proposition "Si \(\mathcal X={\Bbb R}\) et \(\mathcal S\) est un ensemble d'indicatrices d'intervalles, alors \(\operatorname{dim}_\text{VC}(\mathcal S)=3\)".
Verso: Si on prend \(a\leqslant b\leqslant c\in{\Bbb R}\), alors il n'existe pas d'intervalle \(I\) tel que $$a,c\in I\quad\text{ et }\quad b\notin I.$$
Bonus:
Carte inversée ?:
END

Exercices

Tester à la main pour les premiers entiers.

\(5\) points n'a pas l'air de marcher \(\to\) reste à le montrer.

Le rectangle qui prend les \(4\) points extrêmes prend aussi forcément le \(5^e\) \(\to\) ok.

Donner la dimension de Vapnik dans le cas suivant :

• \(\mathcal A\) : la classe des demi-espaces dans \({\Bbb R}^d\).

C'est un cas du cours, qui nous donne une majoration.

Il reste à montrer que cette borne est atteinte.